#include <vector>

namespace zh
{
	class UnionFindSet
	{
	public:
		UnionFindSet(size_t n)
			:_ufs(n,-1)
		{}
		void Union(int x1,int x2)
		{
			int root1 = FindRoot(x1);
			int root2 = FindRoot(x2);
			if (root1 == root2)
				return;
			else
			{
				if (abs(_ufs[root1]) > abs(_ufs[root2]))
					std::swap(root1, root2);
				_ufs[root2] += _ufs[root1];
				_ufs[root1] = root2;
			}
		}
		int FindRoot(int x)
		{
			int root = x;
			while (_ufs[root] >= 0)
			{
				root = _ufs[root];
			}
			int index = 0;
			while (_ufs[x] >= 0)
			{
				index = _ufs[x];
				_ufs[x] = root;
				x = index;
			}
			return root;
		}
		bool InSet(int x1,int x2)
		{
			int root1 = FindRoot(x1);
			int root2 = FindRoot(x2);
			if (root1 == root2)
				return true;
			else
				return false;
		}
		size_t Setsize()
		{
			size_t size = 0;
			for (auto e : _ufs)
			{
				if (e < 0)
					++size;
			}
			return size;
		}
	private:
		std::vector<int> _ufs;
	};
}